package com.huyi.sortMethod;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SortMethodDemo {

	public static void main(String[] args) {
		
		int[] sortData = {56, 41, 100, 85, 2, 99, 78};
		
		// collections工具类排序
		collectionsSort(sortData);
		
		// 直接插入排序法(待定)
		insertSort(sortData);
		
		// 冒泡排序
		bubbleSort(sortData);
		
		// 快速排序
		quickSort(sortData);
		
		
	}

	/**
	 * collections工具类排序方法
	 * 
	 * @param sortData
	 */
	private static void collectionsSort(int[] sortData) {
		List<Integer> resultList = new ArrayList<Integer>(sortData.length);
		for (int s : sortData) {
		    resultList.add(s);
		}
		
		Collections.sort(resultList);
		System.out.println("[collections工具类排序方法]--排序后的数组为："+Arrays.toString(resultList.toArray()));
	}
	
	/**
	 * 直接插入排序法
	 * 
	 * @param sortData
	 */
	private static void insertSort(int[] sortData) {
		// int[] sortData = {56, 41, 100, 85, 2, 99, 78};
		int len = sortData.length;
		if (len == 0) {
			return;
		}
		int insertNum;// 要插入的数
		for (int i = 1; i < len; i++) {
			insertNum = sortData[i];

			// 序列元素个数
			int j = i - 1;
			while (j >= 0 && sortData[j] > insertNum) {// 从后往前循环，将大于insertNum的数向后移动
				sortData[j + 1] = sortData[j];// 元素向后移动
				j--;
			}
			sortData[j + 1] = insertNum;// 找到位置，插入当前元素

		}

		System.out.println("[直接插入排序法]--排序后的数组为：" + Arrays.toString(sortData));
	}

	/**
	 * 冒泡排序法
	 * 
	 * @param sortData
	 */
	private static void bubbleSort(int[] sortData) {

		// int[] sortData = {56, 41, 100, 85, 2, 99, 78};

		// 将序列中所有元素两两比较，将最大的放在最后面。将剩余序列中所有元素两两比较，将最大的放在最后面。重复第二步，直到只剩下一个数。
		int len = sortData.length;
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len - 1 - i; j++) {
				if (sortData[j] > sortData[j + 1]) {
					int temp = sortData[j];
					sortData[j] = sortData[j + 1];
					sortData[j + 1] = temp;
				}
			}
		}
		System.out.println("[冒泡排序法-1]--排序后的数组为：" + Arrays.toString(sortData));
		
		// 将序列中所有元素两两比较，将最小的放在最前面。将剩余序列中所有元素两两比较，将最小的放在最前面。重复第二步，直到只剩下一个数。
		for (int i = 0; i < len; i++) {
			for (int j = i + 1; j < len; j++) {
				if (sortData[j - 1] > sortData[j]) {
					int temp = sortData[j];
					sortData[j] = sortData[j - 1];
					sortData[j - 1] = temp;
				}
			}
		}
		System.out.println("[冒泡排序法-2]--排序后的数组为：" + Arrays.toString(sortData));
	}
	
	/**
	 * 快速排序法
	 * 
	 * @param sortData
	 */
	private static void quickSort(int[] sortData) {
		
		quick(sortData, 0, sortData.length - 1);
		System.out.println("[快速排序法]--排序后的数组为：" + Arrays.toString(sortData));
	}
	
	/**
	 * 递归
	 * 
	 * @param a
	 * @param start
	 * @param end
	 */
	private static void quick(int[] a, int start, int end) {
		if (start < end) {
			int baseNum = a[start];// 选基准值
			int midNum;// 记录中间值
			int i = start;
			int j = end;
			do {
				while ((a[i] < baseNum) && i < end) {
					i++;
				}
				while ((a[j] > baseNum) && j > start) {
					j--;
				}
				if (i <= j) {
					midNum = a[i];
					a[i] = a[j];
					a[j] = midNum;
					i++;
					j--;
				}
			} while (i <= j);
			if (start < j) {
				quick(a, start, j);
			}
			if (end > i) {
				quick(a, i, end);
			}
		}
	}
}
